import sys
import random
from datetime import datetime
from argparse import ArgumentParser
from common import format_timedelta


def quick_sort(a, p, r):
    def rand_partition(a, p, r):
        i = random.choice(range(p, r))
        a[r], a[i] = a[i], a[r]
        x = a[r]
        i = p - 1
        for j in range(p, r):
            if a[j] <= x:
                i += 1
                a[i], a[j] = a[j], a[i]
        a[i + 1], a[r] = a[r], a[i + 1]
        return i + 1

    if p < r:
        q = rand_partition(a, p, r)
        quick_sort(a, p, q - 1)
        quick_sort(a, q + 1, r)


def quick_sort_improve(a, p, r):
    def rand_partition(a, p, r):
        i = random.choice(range(p, r))
        a[r], a[i] = a[i], a[r]
        x = a[r]
        i = p - 1
        for j in range(p, r):
            if a[j] <= x:
                i += 1
                a[i], a[j] = a[j], a[i]
        a[i + 1], a[r] = a[r], a[i + 1]
        return i + 1

    if p < r:
        q = rand_partition(a, p, r)

        # 若数组中最大、最小元素相同，直接结束
        # partition后，最小元素在左，最大元素在右，寻找最小、最大复杂度为O(n)，不增加额外复杂度
        min_value = a[p]
        for i in range(p + 1, q):
            if a[i] < min_value:
                min_value = a[i]
        max_value = a[r]
        for i in range(q, r):
            if a[i] > max_value:
                max_value = a[i]
        if min_value == max_value:
            return

        quick_sort(a, p, q - 1)
        quick_sort(a, q + 1, r)


def quick_sort_wrapper(a, algorithm):
    start_time = datetime.now()
    algorithm(a, 0, len(a) - 1)
    end_time = datetime.now()
    return end_time - start_time


def test_case_1(n=1000000, algorithm=quick_sort):
    print('测试用例1：输入为%d个随机32位整数' % (n,))
    a = [random.randint(0, sys.maxsize) for _ in range(n)]
    timedelta = quick_sort_wrapper(a, algorithm)
    print('用时：' + format_timedelta(timedelta))


def test_case_2(n=1000000, algorithm=quick_sort):
    print('测试用例2：输入为%d个1' % (n,))
    a = [1 for _ in range(n)]
    timedelta = quick_sort_wrapper(a, algorithm)
    print('用时：' + format_timedelta(timedelta))


def test_case_3_inner(n=10000, algorithm=quick_sort):
    print('输入规模为%d' % (n,))
    for j in range(5, 11):
        a = [1 if i < (j * n / 10) else random.randint(0, sys.maxsize) for i in range(n)]
        timedelta = quick_sort_wrapper(a, algorithm)
        print(str(j) + '0%为1，用时：' + format_timedelta(timedelta))


def test_case_3(algorithm=quick_sort):
    print('测试用例3：')
    test_case_3_inner(10000, algorithm)


def test_case_4(algorithm=quick_sort):
    print('测试用例4：')
    test_case_3_inner(1000, algorithm)
    test_case_3_inner(5000, algorithm)


if __name__ == '__main__':
    parser = ArgumentParser()
    parser.add_argument('--random_seed', type=int, default=19950125)
    parser.add_argument('--recursion_limit', type=int, default=100000)
    parser.add_argument('--test_case', type=int, default=1)
    parser.add_argument('--improve', action='store_true')
    parser.add_argument('--input_file', type=str, default='')
    option = parser.parse_args()

    sys.setrecursionlimit(option.recursion_limit)
    random.seed(option.random_seed)

    algorithm = quick_sort_improve if option.improve else quick_sort

    if option.input_file.strip() == '':
        # 运行指导书中测试用例
        [test_case_1, test_case_2, test_case_3, test_case_4][option.test_case - 1](algorithm=algorithm)
    else:
        # 运行现场编写的测试用例
        a = [int(line.strip()) for line in open(option.input_file, 'r')]
        timedelta = quick_sort_wrapper(a, algorithm)
        print('输出：' + str(a))
        print('用时：' + format_timedelta(timedelta))
